#include <stdio.h>
#include <malloc.h>
#include <mqoai.h>

typedef char VertexType; // 顶点类型用户可自定义
typedef int EdgeType; // 边上的权值类型用户可自定义
#define MAXVEX 9

Boolean visited[MAXVEX];

typedef struct EdgeNode {
    int adjVex;
    EdgeType info;
    struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode{
    VertexType data;
    struct EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numNodes, numEdges;
}GraphAdjList;

void DFS(GraphAdjList GL, int i) {
    EdgeNode *p;
    visited[i] = TRUE;
    printf("%c", GL.adjList[i].data);
    // p指向当前顶点指向的下一个结点
    p = GL.adjList[i].firstEdge;
    while (p) {
        // 对未被访问过的结点递归调用
        if(!visited[p->adjVex]) {
            DFS(GL, p->adjVex);
        }
        // 访问过的就沿边表往后走
        p = p->next;
    }
}

void DFSTraverse(GraphAdjList GL) {
    int i;
    for (i = 0; i < GL.numNodes; i++) {
        visited[i] = FALSE;
    }
    for (i = 0; i < GL.numNodes ; i++) {
        if(!visited[i]) {
            DFS(GL, i);
        }
    }
}
